1. Field of the Invention
The present invention relates to an energy-efficient CAM architecture that provides increased speed of searching, reduced power consumption, or a combination of increased speed of searching and reduced power consumption.
2. Description of the Related Art
A Content Addressable Memory (CAM) facilitates search operations based on the content, rather than the physical location of the data. This allows for much faster database operations, such as insertion, deletion, and search. The speed improvement primarily comes from the ability to search multiple entries in parallel. Although the speed of the operation is improved, very large CAMs cannot be built due to energy and power limitations. This is due to the 100% activity factor CAMs have during their search operation. At some point, it becomes technologically infeasible to dissipate the amount of power required for the CAM. For example, some recent CAMs yield a 150 W power consumption projection for a 256 KB CAM, nearly at the limit of conventional cooling for any IC. Although sophisticated circuit design techniques, such as pipelining and banking can reduce this number to a smaller value, such as 50 W, it is still evident that a CAM in the order of Gigabytes is not feasible using today's technology.
CAMs provide the payload associated with a key. As an example, if one was to use a CAM to store zip codes and their associated city names, the key would be the city names, and the zip codes would be the payload (i.e., the result of the search). A conventional CAM is shown in FIG. 1, where the term tag is used interchangeably with the key. A traditional N-entry CAM searches all N elements in a single cycle to match a single key, thus performing N−1 wasteful searches. Therefore, this approach is very energy inefficient. One potential improvement is to use a conventional banked CAM structure as shown in FIG. 2, where the prefix of the data element (e.g., the MSB 4 bits) is used to pre-eliminate a large portion of the banks (e.g., 15). Only a single bank actually performs the query. This approach has a drawback: Since certain data elements can only reside in certain banks, the effective size of the CAM could be drastically reduced for non-uniformly distributed data elements (e.g., having a lot more city names that start with the letter M). This concept of not being able to place a certain entry into a certain bank is defined as a “bank conflict.” This asymmetric distribution of the entries could eventually negate the savings from banking.
A variant of CAM, the ternary CAM (TCAM) stores each element in two bits, allowing three-valued (i.e., ‘0’, ‘1’, ‘x’) logical operations. This style CAM enables additional operations at the expense of storage area and power penalty. Due to the size limitation, CAM/TCAMs have been confined into a limited application space, such as, network routers, to perform packet classification and routing. In network router applications, much smaller (T)CAMs are needed and the search speed is of primary concern, reducing the negative impact of the high power consumption.
There has been considerable work in the area of CAM design to reduce the power and/or energy consumption of (T)CAMs. Although numerous techniques have been proposed to make CAMs more energy-efficient, the power savings have been limited, thereby significantly narrowing the application space of CAMs.
A need arises for an energy-efficient CAM architecture that provides increased speed of searching, reduced power consumption, or a combination of increased speed of searching and reduced power consumption. In addition, a need arises for a CAM architecture that reduces bank conflicts in a banked CAM.